package com.clstu.leetcode;

import java.util.Arrays;

/**
 * 堆排序
 */
class Solution10 {

    public static void main(String[] args) {
        int[] nums = {9,8,7,6,5,4,3,2,1,0,4,5,2,0,9};
        heapSort(nums);
        System.out.println(Arrays.toString(nums));
    }

//    //写一个堆排序(降序)
//    public static void heapSort(int[] nums){
//        //先将数组整成堆结构
//        for(int i=nums.length/2;i>=0;i--){
//             heapfy(nums,i,nums.length);
//        }
//        //循环将小的数放到堆尾部
//        for(int heapSzie = nums.length ; heapSzie>1 ;heapSzie--){
//             swap(nums,0,heapSzie-1);
//             heapfy(nums,0,heapSzie-1);
//        }
//    }
//
//    //手写堆排序中的heapfy,假设index之后的位置都维持了堆结构
//    public static void heapfy(int[] nums,int index,int heapSzie){
//        //一路向下找,将小孩子们向上提,
//        int temp = nums[index];
//        for(int i = index*2+1;i<heapSzie;i = i*2+1){
//            //找到更小的孩子
//            if(i+1 < heapSzie && nums[i+1]<nums[i]) i++;
//            //跟更小的孩子pk
//            if(nums[i] < temp){
//                nums[(i-1)/2] = nums[i];
//                //记录最后一个向上提的位置,提不动了自己就确定到这个位置上
//                index = i;
//            } else{
//                break;
//            }
//        }
//        //自己到
//        nums[index] = temp;
//    }

    //实现堆排序
    public static void heapSort(int[] nums){
        //先变为堆结构
        for(int i=nums.length/2; i>=0; i--){
            heapfy(nums,i,nums.length);
        }
        System.out.println(Arrays.toString(nums));
        //逐个最小的调整到堆尾
        for(int heapSize = nums.length; heapSize>1;heapSize--){
            swap(nums,0,heapSize-1);
            heapfy(nums,0,heapSize-1);
            System.out.println(Arrays.toString(nums));
        }
    }

    //编写方法实现heapfy(小根堆版本)
    public static void heapfy(int[] nums, int index, int heapSize){
        int temp = nums[index];
        for(int i=index*2+1;i<heapSize;i=i*2+1){
            if(i+1 < heapSize && nums[i+1]<nums[i]) i++;
            //更小的孩子跟temp pk
            if(nums[i] < temp){
                nums[index] = nums[i];
                index = i;
            }else{
                break;
            }
        }
        nums[index] = temp;
    }


    public static void swap(int[] nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
